package my.algo.string;

public class StringCmp {

    private static int bruteForce(String s1, String s2) {
        char[] c1 = s1.toCharArray();
        char[] c2 = s2.toCharArray();
        if (c2.length > c1.length) {
            return -1;
        }
        for (int i = 0, j = 0; i < c1.length && j < c2.length;) {
           if (c1[i] == c2[j]) {
               i++;
               j++;
           } else {
               i = i - j + 1;
               j = 0;
           }
           if (j == c2.length) {
               return i - j;
           }
        }
        return -1;
    }

    public static int kmp(String str, String pattern) {
        //预处理，生成next数组
        int[] next = getNexts(pattern);
        int j = 0;
        //主循环，遍历主串字符
        for (int i = 0; i < str.length(); i++) {
            while (j > 0 && str.charAt(i) != pattern.charAt(j)) {
                //遇到坏字符时，查询next数组并改变模式串的起点
                j = next[j];
            }
            if (str.charAt(i) == pattern.charAt(j)) {
                j++;
            }
            if (j == pattern.length()) {
                //匹配成功，返回下标
                return i - pattern.length() + 1;
            }
        }
        return -1;
    }

    private static int[] getNexts(String pattern) {
        int[] next = new int[pattern.length()];
        int j = 0;
        for (int i = 2; i < pattern.length(); i++) {
            // 必须使用回溯 例如ABCAABCABC
            while (j != 0 && pattern.charAt(j) != pattern.charAt(i-1)) {
                //从next[i+1]的求解回溯到 next[j]
                j = next[j];
            }
            if (pattern.charAt(j) == pattern.charAt(i-1)) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }

    public static void main(String[] args) {
//        String s1 = "aaaaaab";
//        String s2 = "aabb";
//        int idx = bruteForce(s1, s2);
//        System.out.println(idx);

        String str = "ATGTGAGCTGGTGTGTGCFAA";
        String pattern = "ABCAABCABC";
        int index = kmp(str, pattern);
        System.out.println("首次出现位置：" + index);
    }
}
